package com.example.gustavo.hello;

import java.util.Arrays;
import java.util.List;

/**
 * Created by gustavo on 2015/1/17.
 */
public class SortUtils {

    /**
     * 快速排序
     *
     * 不稳定
     *      快速排序的时间复杂度为O(nlogn)。     当n较大时使用快排比较好，当序列基本有序时用快排反而不好
     *
     * 取数组第一个值作为基准值,逐一将数组其他元素与之比较,大的放在它的右边,小的放在左边;
     * 然后以它所处的位置将数组分为两部分,进行同样的比较(即递归).
     *
     * @param nums
     */
    public static void quickSort(int[] nums) {
        if (nums != null && nums.length > 1){
            sortQuick(nums, 0, nums.length - 1);
        }

    }
    public static void quickSort(Integer[] nums) {
        if (nums != null && nums.length > 1){
            sortQuick(nums, 0, nums.length - 1);
        }

    }
    private static void sortQuick(int[] nums, int left, int right){
        if(left < right){

            int start = left;
            int end = right;
            int temp = nums[left];

            while (left < right){

                while (left < right && nums[right] >= temp ){//此时 temp = nums[left]
                    right--;

                }
                nums[left] = nums[right];
//                nums[right] = temp;//之后right值不变,nums[right]被重新赋值,故此处可以不赋值;

                while (left < right &&  nums[left] <= temp){//此时 temp = nums[right]
                    left++;
                }
                nums[right] = nums[left];
                nums[left] = temp;

            }
            //递归调用
            sortQuick(nums,start,left-1);
            sortQuick(nums,left+1,end);
        }
    } private static void sortQuick(Integer[] nums, int left, int right){
        if(left < right){

            int start = left;
            int end = right;
            int temp = nums[left];

            while (left < right){

                while (left < right && nums[right] >= temp ){//此时 temp = nums[left]
                    right--;

                }
                nums[left] = nums[right];
//                nums[right] = temp;//之后right值不变,nums[right]被重新赋值,故此处可以不赋值;

                while (left < right &&  nums[left] <= temp){//此时 temp = nums[right]
                    left++;
                }
                nums[right] = nums[left];
                nums[left] = temp;

            }
            //递归调用
            sortQuick(nums,start,left-1);
            sortQuick(nums,left+1,end);
        }
    }
}
